SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Graph factorization</title>

</head>

Graph factorization

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Factor_graph" title="Factor graph">Factor graph</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .unsolved{margin:0.5em 0 1em 1em;border:1px solid #a2a9b1;padding:0.35em 0.35em 0.35em 2.2em;background-color:var(--background-color-interactive-subtle);background-image:url("./mw/Question%2C_Web_Fundamentals.svg");background-position:top 50%left 0.35em;background-size:1.5em;background-repeat:no-repeat}@media(min-width:720px){.mw-parser-output .unsolved{clear:right;float:right;max-width:25%}}.mw-parser-output .unsolved-label{font-weight:bold}.mw-parser-output .unsolved-body{margin:0.35em;font-style:italic}.mw-parser-output .unsolved-more{font-size:smaller}

/* end https://en.wikipedia.org/ */

</style>

<div>Unsolved problem in mathematics</div>

<div class="unsolved-body">Conjecture: If n is odd and k ≥ n, then G is 1-factorable. If n is even and k ≥ n − 1 then G is 1-factorable.</div>

<div class="unsolved-more"><a href="List_of_unsolved_problems_in_mathematics" title="List of unsolved problems in mathematics">More unsolved problems in mathematics</a></div>

</div>

In <a href="Graph_theory" title="Graph theory">graph theory</a>, a factor of a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> G is a <a href="Spanning_subgraph" class="mw-redirect" title="Spanning subgraph">spanning subgraph</a>, i.e., a subgraph that has the same vertex set as G. A k-factor of a graph is a spanning k-<a href="Regular_graph" title="Regular graph">regular</a> subgraph, and a k-factorization partitions the edges of the graph into disjoint k-factors. A graph G is said to be k-factorable if it admits a k-factorization. In particular, a 1-factor is a <a href="Perfect_matching" title="Perfect matching">perfect matching</a>, and a 1-factorization of a k-regular graph is a <a href="Edge_coloring" title="Edge coloring">proper edge coloring</a> with k colors. A 2-factor is a collection of disjoint <a href="Cycle_(graph_theory)" title="Cycle (graph theory)">cycles</a> that spans all vertices of the graph.

<div class="mw-heading mw-heading2"><h2 id="1-factorization">1-factorization</h2></div>

If a graph is 1-factorable then it has to be a <a href="Regular_graph" title="Regular graph">regular graph</a>. However, not all regular graphs are 1-factorable. A k-regular graph is 1-factorable if it has <a href="Chromatic_index" class="mw-redirect" title="Chromatic index">chromatic index</a> k; examples of such graphs include:

<ul><li>Any regular <a href="Bipartite_graph" title="Bipartite graph">bipartite graph</a>.<a href="#cite_note-1">[1]</a> <a href="Hall's_marriage_theorem" title="Hall's marriage theorem">Hall's marriage theorem</a> can be used to show that a k-regular bipartite graph contains a perfect matching. One can then remove the perfect matching to obtain a (k − 1)-regular bipartite graph, and apply the same reasoning repeatedly.</li>

<li>Any <a href="Complete_graph" title="Complete graph">complete graph</a> with an <a href="Parity_(mathematics)" title="Parity (mathematics)">even</a> number of nodes (see <a href="#Complete_graphs">below</a>).<a href="#cite_note-2">[2]</a></li></ul>

However, there are also k-regular graphs that have chromatic index k + 1, and these graphs are not 1-factorable; examples of such graphs include:

<ul><li>Any regular graph with an <a href="Parity_(mathematics)" title="Parity (mathematics)">odd</a> number of nodes.</li>

<li>The <a href="Petersen_graph" title="Petersen graph">Petersen graph</a>.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Complete_graphs">Complete graphs</h3></div>

A 1-factorization of a <a href="Complete_graph" title="Complete graph">complete graph</a> corresponds to pairings in a <a href="Round-robin_tournament" title="Round-robin tournament">round-robin tournament</a>. The 1-factorization of complete graphs is a special case of <a href="Baranyai's_theorem" title="Baranyai's theorem">Baranyai's theorem</a> concerning the 1-factorization of complete <a href="Hypergraph" title="Hypergraph">hypergraphs</a>.

One method for constructing a 1-factorization of a complete graph on an even number of vertices involves placing all but one of the vertices in a <a href="Regular_polygon" title="Regular polygon">regular polygon</a>, with the remaining vertex at the center. With this arrangement of vertices, one way of constructing a 1-factor of the graph is to choose an edge e from the center to a single polygon vertex together with all possible edges that lie on lines perpendicular to e. The 1-factors that can be constructed in this way form a 1-factorization of the graph.

The number of distinct 1-factorizations of K2, K4, K6, K8, ... is 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... (<a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="https://oeis.org/A000438" class="extiw external" title="oeis:A000438">A000438</a>).

<div class="mw-heading mw-heading3"><h3 id="1-factorization_conjecture">1-factorization conjecture</h3></div>

Let G be a k-regular graph with 2n nodes. If k is sufficiently large, it is known that G has to be 1-factorable:

<ul><li>If k = 2n − 1, then G is the complete graph K2n, and hence 1-factorable (see <a href="#Complete_graphs">above</a>).</li>

<li>If k = 2n − 2, then G can be constructed by removing a perfect matching from K2n. Again, G is 1-factorable.</li>

<li><a href="#CITEREFChetwyndHilton1985">Chetwynd & Hilton (1985)</a> show that if k ≥ 12n/7, then G is 1-factorable.</li></ul>

The 1-factorization conjecture<a href="#cite_note-3">[3]</a> is a long-standing <a href="Conjecture" title="Conjecture">conjecture</a> that states that k ≈ n is sufficient. In precise terms, the conjecture is:

<ul><li>If n is odd and k ≥ n, then G is 1-factorable. If n is even and k ≥ n − 1 then G is 1-factorable.</li></ul>

The <a href="Overfull_conjecture" class="mw-redirect" title="Overfull conjecture">overfull conjecture</a> implies the 1-factorization conjecture.

The conjecture was confirmed by Csaba, Kühn, Lo, Osthus and Treglown for sufficiently large n.<a href="#cite_note-csaba-4">[4]</a>

<div class="mw-heading mw-heading3"><h3 id="Perfect_1-factorization">Perfect 1-factorization</h3></div>

A perfect pair from a 1-factorization is a pair of 1-factors whose union <a href="Glossary_of_graph_theory#Subgraphs" title="Glossary of graph theory">induces</a> a <a href="Hamiltonian_cycle" class="mw-redirect" title="Hamiltonian cycle">Hamiltonian cycle</a>.

A perfect 1-factorization (P1F) of a graph is a 1-factorization having the property that every pair of 1-factors is a perfect pair. A perfect 1-factorization should not be confused with a perfect matching (also called a 1-factor).

In 1964, <a href="Anton_Kotzig" title="Anton Kotzig">Anton Kotzig</a> conjectured that every complete graph K2n where n ≥ 2 has a perfect 1-factorization. So far, it is known that the following graphs have a perfect 1-factorization:<a href="#cite_note-wallis-5">[5]</a>

<ul><li>the infinite family of complete graphs K2p where p is an odd <a href="Prime_number" title="Prime number">prime</a> (by Anderson and also Nakamura, independently),</li>

<li>the infinite family of complete graphs Kp+1 where p is an odd prime,</li>

<li>and sporadic additional results, including K2n where 2n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Some newer results are collected <a rel="nofollow" class="external text" href="http://users.monash.edu.au/~iwanless/data/P1F/newP1F.html">here</a>.</li></ul>

If the complete graph Kn+1 has a perfect 1-factorization, then the <a href="Complete_bipartite_graph" title="Complete bipartite graph">complete bipartite graph</a> Kn,n also has a perfect 1-factorization.<a href="#cite_note-wanless-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="2-factorization">2-factorization</h2></div>

If a graph is 2-factorable, then it has to be 2k-regular for some integer k. <a href="Julius_Petersen" title="Julius Petersen">Julius Petersen</a> showed in 1891 that this necessary condition is also sufficient: <a href="2-factor_theorem" title="2-factor theorem">any 2k-regular graph is 2-factorable</a>.<a href="#cite_note-7">[7]</a>

If a <a href="Connectivity_(graph_theory)" title="Connectivity (graph theory)">connected graph</a> is 2k-regular and has an even number of edges it may also be k-factored, by choosing each of the two factors to be an alternating subset of the edges of an <a href="Euler_tour" class="mw-redirect" title="Euler tour">Euler tour</a>.<a href="#cite_note-8">[8]</a> This applies only to connected graphs; disconnected <a href="Counterexample" title="Counterexample">counterexamples</a> include disjoint unions of odd cycles, or of copies of K2k+1.

The <a href="Oberwolfach_problem" title="Oberwolfach problem">Oberwolfach problem</a> concerns the existence of 2-factorizations of complete graphs into <a href="Graph_isomorphism" title="Graph isomorphism">isomorphic</a> subgraphs. It asks for which subgraphs this is possible. This is known when the subgraph is connected (in which case it is a <a href="Hamiltonian_cycle" class="mw-redirect" title="Hamiltonian cycle">Hamiltonian cycle</a> and this special case is the problem of <a href="Hamiltonian_decomposition" title="Hamiltonian decomposition">Hamiltonian decomposition</a>) but the general case remains <a href="Open_problem" title="Open problem">open</a>.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <a href="#CITEREFHarary1969">Harary (1969)</a>, Theorem 9.2, p. 85. <a href="#CITEREFDiestel2005">Diestel (2005)</a>, Corollary 2.1.3, p. 37.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <a href="#CITEREFHarary1969">Harary (1969)</a>, Theorem 9.1, p. 85.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a href="#CITEREFChetwyndHilton1985">Chetwynd & Hilton (1985)</a>. <a href="#CITEREFNiessen1994">Niessen (1994)</a>. <a href="#CITEREFPerkovicReed1997">Perkovic & Reed (1997)</a>. <a href="#West1FC">West</a>.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCsabaKühnLoOsthus2016" class="citation cs2">Csaba, Béla; Kühn, Daniela; Lo, Allan; Osthus, Deryk; Treglown, Andrew (June 2016), "Proof of the 1-factorization and Hamilton decomposition conjectures", Memoirs of the American Mathematical Society, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fmemo%2F1154">10.1090/memo/1154</a></cite>

</li>

<cite id="CITEREFWallis1997" class="citation cs2">Wallis, W. D. (1997), "16. Perfect Factorizations", One-factorizations, Mathematics and Its Applications, vol. 390 (1 ed.), <a href="Springer_US" class="mw-redirect" title="Springer US">Springer US</a>, p. 125, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4757-2564-3_16">10.1007/978-1-4757-2564-3_16</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7923-4323-3</bdi></cite>

</li>

<cite id="CITEREFBryantMaenhautWanless2002" class="citation cs2">Bryant, Darryn; Maenhaut, Barbara M.; Wanless, Ian M. (May 2002), "A Family of Perfect Factorisations of Complete Bipartite Graphs", Journal of Combinatorial Theory, A, 98 (2): 328–342, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcta.2001.3240">10.1006/jcta.2001.3240</a>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-3165">0097-3165</a></cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <a href="#CITEREFPetersen1891">Petersen (1891)</a>, §9, p. 200. <a href="#CITEREFHarary1969">Harary (1969)</a>, Theorem 9.9, p. 90. See <a href="#CITEREFDiestel2005">Diestel (2005)</a>, Corollary 2.1.5, p. 39 for a proof.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <a href="#CITEREFPetersen1891">Petersen (1891)</a>, §6, p. 198.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Bibliography">Bibliography</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFBondyMurty1976" class="citation cs2"><a href="John_Adrian_Bondy" title="John Adrian Bondy">Bondy, John Adrian</a>; <a href="U._S._R._Murty" title="U. S. R. Murty">Murty, U. S. R.</a> (1976), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100413104345/http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html">Graph Theory with Applications</a>, North-Holland, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-444-19451-7</bdi>, archived from <a rel="nofollow" class="external text" href="https://archive.org/details/graphtheorywitha0000bond">the original</a> on 2010-04-13, retrieved 2019-12-18</cite>, Section 5.1: "Matchings".</li>

<li><cite id="CITEREFChetwyndHilton1985" class="citation cs2"><a href="Amanda_Chetwynd" title="Amanda Chetwynd">Chetwynd, A. G.</a>; Hilton, A. J. W. (1985), "Regular graphs of high degree are 1-factorizable", Proceedings of the London Mathematical Society, 50 (2): 193–206, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2Fplms%2Fs3-50.2.193">10.1112/plms/s3-50.2.193</a></cite>.</li>

<li><cite id="CITEREFDiestel2005" class="citation cs2"><a href="Reinhard_Diestel" title="Reinhard Diestel">Diestel, Reinhard</a> (2005), Graph Theory (3rd ed.), <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-26182-6</bdi></cite>, Chapter 2: "Matching, covering and packing". <a rel="nofollow" class="external text" href="http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/">Electronic edition</a>.</li>

<li><cite id="CITEREFHarary1969" class="citation cs2"><a href="Frank_Harary" title="Frank Harary">Harary, Frank</a> (1969), Graph Theory, Addison-Wesley, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-02787-9</bdi></cite>, Chapter 9: "Factorization".</li>

<li><cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php?title=One-factorization">"One-factorization"</a>, <a href="Encyclopedia_of_Mathematics" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a>, <a href="European_Mathematical_Society" title="European Mathematical Society">EMS Press</a>, 2001 [1994]</cite></li>

<li><cite id="CITEREFNiessen1994" class="citation cs2">Niessen, Thomas (1994), "How to find overfull subgraphs in graphs with large maximum degree", Discrete Applied Mathematics, 51 (1–2): 117–125, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0166-218X%2894%2990101-5">10.1016/0166-218X(94)90101-5</a></cite>.</li>

<li><cite id="CITEREFPerkovicReed1997" class="citation cs2 cs1-prop-long-vol">Perkovic, L.; <a href="Bruce_Reed_(mathematician)" title="Bruce Reed (mathematician)">Reed, B.</a> (1997), "Edge coloring regular graphs of high degree", <a href="Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a>, 165–166: 567–578, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0012-365X%2896%2900202-6">10.1016/S0012-365X(96)00202-6</a></cite>.</li>

<li><cite id="CITEREFPetersen1891" class="citation cs2"><a href="Julius_Petersen" title="Julius Petersen">Petersen, Julius</a> (1891), <a rel="nofollow" class="external text" href="https://zenodo.org/record/2304433/files/article.pdf">"Die Theorie der regulären graphs"</a> (PDF), <a href="Acta_Mathematica" title="Acta Mathematica">Acta Mathematica</a>, 15: 193–220, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02392606">10.1007/BF02392606</a></cite>.</li>

<li><cite id="West1FC" class="citation web cs1">West, Douglas B. <a rel="nofollow" class="external text" href="http://www.math.uiuc.edu/~west/openp/1fact.html">"1-Factorization Conjecture (1985?)"</a>. Open Problems – Graph Theory and Combinatorics. Retrieved 2010-01-09.</cite></li>

<li><cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/GraphFactor.html">"Graph Factor"</a>. <a href="MathWorld" title="MathWorld">MathWorld</a>.</cite></li>

<li><cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/k-Factor.html">"k-Factor"</a>. <a href="MathWorld" title="MathWorld">MathWorld</a>.</cite></li>

<li><cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/k-FactorableGraph.html">"k-Factorable Graph"</a>. <a href="MathWorld" title="MathWorld">MathWorld</a>.</cite></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFPlummer2007" class="citation cs2"><a href="Michael_D._Plummer" title="Michael D. Plummer">Plummer, Michael D.</a> (2007), "Graph factors and factorization: 1985–2003: A survey", <a href="Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a>, 307 (7–8): 791–821, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disc.2005.11.059">10.1016/j.disc.2005.11.059</a></cite>.</li></ul>

</div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-19" href="https://en.wikipedia.org/wiki/?title=Graph_factorization&oldid=1296319821">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>